package practice1_100;

import java.util.Arrays;

public class Xiecheng {
    public double  test(int row,int column){
        double[][] matrix=new  double[row][column];
        //Arrays.fill(matrix,-1);
        matrix[row-1][column-1]=1;
        double a= dp(matrix,0,0);
        return a;
    }
    public double dp(double[][] matix,int row,int column){
        double p=0;
        if(row>= matix.length||column>=matix[0].length) return 0;
        if(row== matix.length-1&&column==matix[0].length-1) return 1;

        //用martix表格作为dp记录表，消除子问题
        if(matix[row][column]!=0) return matix[row][column];

        p+= dp(matix,row,column+1)*0.25+dp(matix,row+1,column)*0.75;
        matix[row][column]=p;
        return matix[row][column];
    }

    public static void main(String[] args) {

        System.out.println(new Xiecheng().test(2,2));

    }
}
